class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        # 定义快速选择函数
        def quickselect(left: int, right: int, k_smallest: int) -> int:
            # 当左指针小于等于右指针时，继续循环
            while left <= right:
                # 随机选择一个基准点
                pivot_index = random.randint(left, right)
                pivot = nums[pivot_index]

                # 三路划分
                lt, i, gt = left, left, right
                # 当i小于等于gt时，继续循环
                while i <= gt:
                    # 如果nums[i]小于基准点，则交换nums[lt]和nums[i]，lt和i都加1
                    if nums[i] < pivot:
                        nums[lt], nums[i] = nums[i], nums[lt]
                        lt += 1
                        i += 1
                    # 如果nums[i]大于基准点，则交换nums[i]和nums[gt]，gt减1
                    elif nums[i] > pivot:
                        nums[i], nums[gt] = nums[gt], nums[i]
                        gt -= 1
                    # 如果nums[i]等于基准点，则i加1
                    else:
                        i += 1

                # 如果k_smallest小于lt，则右指针等于lt-1
                if k_smallest < lt:
                    right = lt - 1
                # 如果k_smallest大于gt，则左指针等于gt+1
                elif k_smallest > gt:
                    left = gt + 1
                # 如果k_smallest在lt和gt之间，则返回nums[k_smallest]
                else:
                    return nums[k_smallest]

        # 获取nums的长度
        n = len(nums)
        # 返回快速选择函数的结果
        return quickselect(0, n - 1, n - k)